public class Leetcode {
}

//leetcode:516:最长回文子序列
class Solution1 {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();

        int[][] dp = new int[n][n];
        for(int i = n-1; i >= 0; i--){
            //任意单个字符都为回文子序列
            dp[i][i] = 1;
            for(int j = i+1; j < n;j++){
                //如果这两个字符相同，那么此时回文串的长度就为这段字符串除它们两个之外的回文字符串的长度加2
                if(s.charAt(i) == s.charAt(j)) dp[i][j] = dp[i+1][j-1] + 2;
                    //如果不相同此时位置的回文串长度就为除去这两个字符任意一个后的回文串最长的那个
                else dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]);
            }
        }
        //最后返回0到n-1这个长度的字符串的最长回文串长度
        return dp[0][n-1];
    }
}

//leetcode:1312:让字符串成为回文串的最小插入次数
class Solution2 {
    public int minInsertions(String s) {
        int n = s.length();

        //创建一个dp表，表示在i到j位置能使字符串成为回文串的最小插入次数
        int[][] dp = new int[n][n];
        for(int i = n-1; i >= 0;i--){
            for(int j = i+1; j < n;j++){
                //如果两个字符相等，此时这两个字符间成为回文串的最小插入次数为，这段区间除它们之外的回文串的最小插入次数
                if(s.charAt(i) == s.charAt(j)) dp[i][j] = dp[i+1][j-1];
                    //如果不等，此时的最小插入次数就只需要去找这个区间内，除去这两个字符中某一个字符后的回文串的最小插入次数，中最小的那个，加1，即在这段区间的最左边填上一个j位置的字符或在最右边填上一个i位置的字符
                else dp[i][j] = Math.min(dp[i+1][j],dp[i][j-1]) + 1;
            }
        }
        //返回0到n-1区间的最小插入次数
        return dp[0][n-1];
    }
}